Messalina là con gái đầu tiên và đứa con thứ hai của Domitia Lepida Trẻ cùng với người anh em họ của bà Marcus Valerius Messalla Barbatus. Mẹ cô là con út của Chấp chính quan Lucius Domitius Ahenobarbus và Antonia Già. Domitius là người chồng đầu tiên của Hoàng hậu tương lai Agrippina Trẻ và cha đẻ của Hoàng đế Nero tương lai, điều này đã khiến Nero trở thành anh họ của Messalina bất chấp việc Messalina hơn ông tới mười bảy tuổi. Gia đình của Messalina khá phức tạp. Bà Claudia Marcella Messalina và Antonia Già là chị em cùng mẹ khác cha. Claudia Marcella, bà nội của Messalina, là con gái của chị gái Augustus, Octavia Trẻ với Gaius Claudius Marcellus nhỏ. Antonia Già, bà ngoại của Messalina, là con gái cả của Octavia với Marcus Antonius, và là dì của hoàng đế Claudius. Do đó, một số lượng lớn thành viên trong gia đình có quan hệ cận huyết.

Có rất ít thông tin về cuộc sống của Messalina trước khi kết hôn với người anh em họ hai đời Claudius vào năm 38, lúc đó ông khoảng 48 tuổi. Hai đứa trẻ được sinh ra như một kết quả của sự kết hợp của họ: một cô con gái tên là Claudia Octavia (sinh năm 39 hoặc 40), là một hoàng hậu tương lai, chị gái và người vợ cả của hoàng đế Nero, và một con trai, Britannicus. Khi Hoàng đế Caligula đã bị sát hại năm 41, thuộc Đội Cận vệ của Hoàng đế tuyên bố Claudius trở thành hoàng đế mới và Messalina trở thành hoàng hậu.